\input ijcai 	% Then CogSciJournal formatting macros
\def\TITL #1{
 \titlepage\ninepoint
 \runninglefthead{#1}
 \vfill
 \advcount8
 \runningrighthead{{ }} 
 \section{{ }}
 \eject
 \ctrline{\:=#1}
	\vskip 4pt plus 2pt
	\acpmark{\chd}{\csec}
	\noindent\ninepoint\!
}
\def\sectionskip{\penalty-60\vskip 3pt plus 2pt minus 1pt}
\def\ASEC #1{
 \titlepage\ninepoint
 \vfill\eject
 \advcount4
 \gdef\grrh{#1}
 \runningrighthead{#1}
 \section{App. \count4 }
 \sectionskip
 \asecbegin{\count4. #1}
 \setcount5 0
% \setcount9 0
 }
\def\NSECP #1{
 \titlepage\ninepoint
 \vfill\eject
 \advcount4
 \gdef\grrh{#1}
 \runningrighthead{#1}
 \section{\count4}
 \sectionskip
 \sectionbegin{\count4. #1}
 \setcount5 0
%	 \setcount9 0      FOR COG SCI, DON'T RESTART FOOTNOTE NUMBERS
 }
\hsize 6xgpin \vsize 8xgpin \maxdepth 2pt \parindent 19pt \topbaseline 10pt
\parskip 20pt plus 3pt minus 1pt \lineskip 8pt
\topskip 27pt plus 5pt minus 2pt  \botskip 3pt plus 9pt
\output{\baselineskip 0pt\lineskip0pt	% beginning of output routine, resets skips
	\vjust to 9.5xgpin{         % prepare the full page of this fixed height
 		\vskip 27pt	% no page nos at top of preface material
		\page 		% insert the page contents
		\vfill		 % extra space before the page number
	}			% completion of the \vjust
	\advcount0}		% increase page number by 1 and end output routine
\jpar 100

\TITL{COGNITIVE  ECONOMY}

%  \vskip 9pt

 \ctrline{\:=In a Fluid Task Environment}

 \vskip 17pt


{\:q Douglas B. Lenat, \  Frederick Hayes-Roth, \  and Philip Klahr}


\vskip 1.5xgpin   	% Footnote material for title page


\eightpoint

\parindent 0pt

Dr. Lenat is an assistant professor in
the Computer Science Department, Stanford University,
Stanford, Ca. 94305.
Drs. Hayes-Roth and Klahr are researchers in the Information Sciences
Department of the Rand Corporation, Santa Monica, Ca.

This paper describes work in progress, sponsored by the National
Science Foundation under grants MCS77-04440 and MCS77-03273.  It is
addressed to a technical audience familiar with the concepts of artificial
intelligence, knowledge representation, and knowledge engineering.  
Although it does present some concrete research results,
it is
being disseminated at this time primarily to stimulate discussion and interaction
with colleagues on these issues.

\ninepoint

\vfill

Running Title:  COGNITIVE ECONOMY


\setcount0 1

\vfill\eject

\output{\baselineskip 0pt\lineskip0pt	% beginning of output routine, resets skips
	\vjust to 8.5xgpin{         % prepare the full page of this fixed height
 		\ctrline{\:c --- \count0 --- }
		\vskip 20pt
		\page 		% insert the page contents
		\vfill		 % extra space before the page number
	}			% completion of the \vjust
	\advcount0}		% increase page number by 1 and end output routine

\tenpoint

{\bf Abstract}

\ninepoint

\vskip 1xgpin  		% Here goes the abstract

\noindent Intelligent systems can explore only tiny subsets of their potential
external and conceptual worlds.  To increase their effective
capacities, they must develop efficient forms of representation,
access, and operation.  
If forced to survive in a changing task environment,
most inferential systems could benefit
from
{\it learning}
about that environment and their own behavior.  For example,
they can exploit new schemata or different slot-names to simplify and
restructure their knowledge.  
In this paper we describe a program that automatically extends its
schematized representation of knowledge, by defining appropriate new slots
dynamically.  We then review some very general techniques for
increasing the efficiency of programs without sacrificing
expressibility:
caching, abstraction, and
expectation-simplified processing.
It is shown in detail how one of these, caching, regains the efficiency that
otherwise would be lost in adopting the interpretive slot-defining scheme
presented earlier.  

\vskip 11pt

\tenpoint

\vfill

\eject

\NSECP{Introduction}

\parindent 19pt

Computer programs, no less than biological creatures, must perform 
in an environment: an externally imposed set of demands, pressures,
opportunities, regularities.
{\it Cognitive economy} is the degree to which a program is adapted to its
environment, the extent to which
its internal capabilities (structures and processes) accurately
and efficiently reflect
its environmental niche.
If the environment changes frequently and radically, then the program
(or species or organization) should monitor those changes and be capable of
adapting itself to them dynamically.  This is cost effective when
the penalty for failure to adapt exceeds the sum of the following
costs: (i) The continuous overhead for monitoring to detect changes,
(ii) The onetime cost of providing a mechanism by which self-modification
can occur, and (iii) The occasional expense of employing that mechanism to
respond to a change which has been observed.  

\vskip 1.5xgpin

% 	Put the equation here -- in a box, with (1) at margin


There are two directions for exploring this phenomenon:

\noindent $\bullet $ 
Make the preceding equation less mushy.  Investigate what features of the
performer (program), task environment, changes in that environment, etc.,
make the ``monitoring & self-modification'' process cost effective.
Clearly, in some cases the penalty
for non-adaptation {\it is} high enough; 
as examples spanning several time scales
consider biological evolution (millenia),
the educational system of a culture (years),
the business meetings of a corporation (months),
the immune system of an organism (hours),
and
the nervous system of an organism (milliseconds).
In other cases, the above equation tips {\it against} adaptation as being
cognitively economical; 
to date, almost all computer programs (and cognitive models in general)
have been constructed to deal with a fixed task, or at least with a
fixed task environment [Newell & Simon 1972].  But the magnitude of the
phenomena we seek to model continues to grow, and we begin to
feel the confines of any single, unchanging model we hypothesize.
In the years ahead, our models --- be they in Lisp, equations, or prose ---
must become increasingly responsive.   In the conclusions of this paper,
we provide some further thoughts on this research direction.

\noindent $\bullet $ 
Operationalize the vague phrase ``monitoring & self-modification.''
In the case of computer models, how might they select (or {\sl discover})
timely new knowledge, new control algorithms,
new knowledge representations?   What are the difficulties encountered?
In this paper we present some
specific techniques by which such programs can monitor their
runtime environment (Appendix 4) 
and modify themselves to heighten their fitness to it (Section 2).
We describe how one particular program, Eurisko, dynamically defines useful
new slots automatically.

\NSECP{Dynamic Self-Modification}


\yskip


{\bf Summary:\  \sl
We illlustrate various ways in which a program might use to
advantage knowledge gleaned dynamically: selecting (or perhaps even {\it 
discovering}) new data structures, representations, and algorithms, which
seem better suited to the current runtime environment, the current user, 
the current problem, etc.}

\yskip

In order for a program to dynamically modify its own
processing, it must examine, integrate and apply knowledge of
the task domain, knowledge about programming in general, knowledge about the
actual runtime environment, and knowledge gathered from observing its own
processing behavior.  Appendix 4 sketches ways in which dynamic program
performance could be self-monitored.  This section draws attention to the
possibility of applying such usage data to modifying --- and in the extreme
re-synthesizing --- the program.

Tasks can be specified anywhere from a pure ``What'' (desired
input/output behavior) to a pure ``How'' (precise algorithms, data structures,
representations, formats).  It has been observed [Feigenbaum 1977] that one
of the goals of AI research is to push our ability from the How end toward
the What end of that spectrum.  This often takes the form of designing a new
very$↑{n+1}$-high level language; i.e., higher
than any that hitherto existed, one which takes over
more of the program implementation.  We can see this as far back as
assemblers replacing machine language, and as recently as KRL [Bobrow and
Winograd 1977] and the Molgen Units Package [Stefik 1978]  extending
Interlisp. 

Assuming, then, that the user
desires merely to specify What, an intelligent language (automatic code
synthesizer) must decide How.  Upon what can it base its design?
Previous efforts have employed knowledge about program transformations
[Burstall and Darlington 1977] [Balzer et al. 1977], programming techniques and
task-specific knowledge [Green and Barstow 1978], and
 --- if the input language is at all complex --- information to enable
the succesful translation of the input specification into a sufficiently
precise specification of What [Lenat 1975].
A couple recent efforts have begun to guide the decision-making during code
synthesis by algorithmic analysis [Kant 1977] or even by aesthetics
[Cohen 1979][Kahn 1979]
[Lenat 1976].  But all these methods are
{\it static}: they feed off a fixed base of initially-supplied knowledge,
heuristics, constraints, suggestions, facts.  The user supplies a
specification for the desired program, and the knowledge base is employed
to produce that target.


What might it mean for a program to modify itself dynamically?
The simplest kind of adaptive abilities along this line would be to {\it select}
a data structure, a representation, or an algorithm from a set of well-known
choices
--- and to reserve the right and the ability to change that decision later.
One could gather knowledge about the relative strengths and weaknesses 
of each choice [Kant 1977].  This knowledge
could be in the form of rules which ask not only about static data, but which
sample the runtime environment of the program as well. See Figure 1.

\vskip 10pt

\noindent ``If
one conjunct appears to be false more often than any other, make it the first
one tested in the conjunction''  

\noindent ``If each person will use the program only
once, briefly, it is not worth building a model of each such user''

\noindent ``A function that is used frequently and changed rarely should be
compiled.''

\noindent ``If items always appear to be accessed in the same order, Then
a sequential data structure is probably adequate for them.''


\vskip 10pt

\ctrline{\bf [FIGURE 1: Environment-driven selection rules]}

\vskip 15pt

Such design questions could in most cases
be answered initially (during program synthesis) but
our suggestion of automating the gathering of such data is a further step
toward the ``What" of artificial intelligence.

There is another possibility, much more exotic than the previous one,
which deserves attention: the automated
discovery --- in ``real time" --- of new
types of data structures and representations which would be useful
for the program in its current environment.

Defining a new data structure is not as difficult as it may first appear:
a data structure can be thought of abstractly in terms of a set of operations
one wants to be able to perform on it (e.g., First, Last, Next, and Previous, for
lists).  The set of desired operations need not be minimal nor concern itself
with which operations are most important, etc.  The run-time usage of such
a data structure can be sampled, and that can guide the search for an
ever more appropriate implementation (e.g., in one usage, it might be
very useful for Last to be efficient, and Interlisp's {\:cTCONC}ing might be
chosen as an implementation; in another
environment, it might be useful for Next and Previous to be efficient, and
a doubly-linked implementation would be best).

The two points here are (i) the implementation of a data structure
may depend upon how it is commonly used in a particular spot in a program,
by a particular user, and (ii) a new kind of data structure may be defined
abstractly merely by selecting a set of operations; this choice, too, can
be made by examining the run-time data as it accumulates (e.g., the final
rule in Fig. 1.)

Defining a new {\it representation} is not quite so neat. 
In fact, humans have only
managed to find a handful of representations to date. In lieu of any constructive
suggestions along that line, we shall focus on {\it extending} a 
given representation:
This appears to be intermediate in difficulty between {\it selecting} a representation and
{\it discovering} a new one.

               \SSEC{Extending a Schematized Representation}


{\bf Summary:\  \sl
The Eurisko program extends it schematized representation
by defining new types of
slots. It uses a very simple grammar for defining new slots from old ones (legal
moves), and a corpus of heuristic rules for
guiding and constraining that process (plausible moves).}

\yskip

For a schematized representation,
``extension" could
occur by defining
new types of slots.  The Eurisko program (an extension of the AM 
program [Lenat 1976]) has this capability, and we shall
briefly describe how this mechanism was developed.

First, we isolated several ways in which new slots are defined from old
ones:

\yskip

\parskip 12pt plus 1pt minus 1pt \lineskip 5pt

\noindent {\bf STAR}  (e.g., Ancestor $=↓{df}$ Parent$↑*$ which means a Parent of a
Parent of... of a Parent of me; the general case should be aparent);

\noindent {\bf UNION} (e.g., Parent $=↓{df}$ Father $\union$ Mother); 

\noindent {\bf COMPOSITION}
(e.g., First-Cousin $=↓{df}$ Child$\circ$Sibling$\circ$Parent; i.e., any
child of any sibling of either of my parents); 

\noindent {\bf DIFFERENCE}
(e.g., Remote-ancestor $=↓{df}$ Ancestor $-$ Parent).

\parskip 20pt plus 3pt minus 1pt \lineskip 8pt

\yskip

These four operators which define new types of slots 
($\,↑*,\  \union,\ \circ,\ -$) are called {\it slot-combiners}.
Other slot-combiners will be mentioned later.

\yskip

Next, we added to Eurisko's knowledge base a concept for each type of slot, and
a concept for each type of slot-combiner. Figure 2 shows some of the
Generalizations and Star concepts. Note in particular the way in which
Generalizations is defined as Genl$↑*$ --- i.e., immediate generalizations,
{\it their} immediate generalizations, and so on. 

\vskip 3.8xgpin

\ctrline{\bf[FIGURE 2: Generalizations and Star concepts]}

% \yyskip

% \yyskip

Finally, we modified the way in which slot entries are accessed.
To illustrate this, we choose a simple task in mathematics, whose paraphrase
is, ``What are all the generalizations of the concept `primes'?"  The
traditional way in which {\:c (GET PRIMES GENERALIZATIONS)} would work is
to examine the property list of {\:c PRIMES}, looking for the attribute
{\:c GENERALIZATIONS}; if found, the entries listed there would be returned.
If, as in Fig. 3, there is no such attribute, the call upon {\:c GET} will
return {\:c NIL} (the empty list).

\vfill\eject

.

\vskip 3.0xgpin


\ctrline{\bf[FIGURE 3: Primes concept]}

\vskip 3.0xgpin

\ctrline{\bf[FIGURE 4: network of concepts from Primes up]}

\yyskip

We modified the
way in which any retrieval request of the form 
{\:c (GET C F)}
operates. In case the 
{\:c F}
 attribute of
{\:c C}
 has no entries (or doesn't exist),  Eurisko examines the definition of
{\:c  F}
and --- if one exists --- try to use it to compute the entries that could
legally be stored on the 
{\:c F}
 attribute of 
{\:c C}.  More precisely, before quitting
we try to 
{\:c (GET F DEFN),}
 and if that succeeds we apply it to 
{\:c C.}
Let's continue the example of 
{\:c (GET PRIMES GENERALIZATIONS).}
 As we
see in Fig. 3 above, there are none recorded. So 
{\:c GET}
 now calls itself
recursively; our original call is replaced by
{\:c ((GET GENERALIZATIONS DEFN)  PRIMES).}
But as Fig. 2 shows, there is no slot labelled 
{\:c DEFN}
 on the concept for
{\:c GENERALIZATIONS}.
So we recur one more time. By now our call has become

{\:c (((GET DEFN DEFN) GENERALIZATIONS) PRIMES).}\foo{I.e.,
get the expression stored in the Defn slot of the Defn concept; call it F.
F should exist, and should be a $\lambda $-expression (a function)
which takes the name of a slot S as argument, and computes a
function which tells how to read slot S for any concept.  Eurisko
applies F to Generalizations, and that yields as a result a new function,
a $\lambda $-expression, call it G. G tells how to find generalizations
of any concept.  In particular, when Eurisko applies G to Primes, the result
is a list of the legal entries for the Generalizations slot of Primes.
Quote marks (') have been omitted for readability.}

Here is part of the 
{\:c DEFN}
 concept:

\vfill\eject

.

\vskip 2.0xgpin

\ctrline{\bf[FIGURE 5: DEFN concept]}

\yyskip


Luckily, it does have a 
{\:c DEFN}
 slot, so we end the recursion.
Applying the entry stored there to the argument ``{\:c GENERALIZATIONS},"
we see our original call becoming transformed into

{\:c [((GET (GET GENERALIZATIONS SLOT-COMBINER) DEFN)}

{\:c \hjust{\hskip 29pt (GET GENERALIZATIONS BUILT-FROM))}}

{\:c \hjust{\hskip 23pt PRIMES]}}

We see from Fig. 2 that
the slot-combiner of Generalizations is ``Star,"
and the argument
(old slot) which it is built from is ``Genl."  So the entire call
shrinks into
{\:c (((GET STAR DEFN) GENL) PRIMES).}
The Star concept has an entry for its Defn slot;
it turns the preceding call into
{\:c (($\lambda$ (c) (AND c (CONS c (self (GET c GENL)))))   PRIMES). }
This function first calls for 
{\:c (GET PRIMES GENL),}
 which is 
{\:c NUMBERS,}
 then calls
itself on 
{\:c NUMBERS;}
 that in turn calls for 
{\:c (GET NUMBERS GENL),}
 which is
{\:c OBJECTS,}
 and calls itself recursively on 
{\:c OBJECTS;}
 that calls for
{\:c (GET OBJECTS GENL),}
 which is 
{\:c ANYTHING,}
 and the next recursive call terminates
when it is discovered that 
{\:c ANYTHING}
 has no 
{\:c GENL}
 (no immediate generalization.)  See Fig. 4.
The list 
{\:c CONS}tructed and returned is thus 
{\:c (PRIMES NUMBERS OBJECTS ANYTHING).}
These four items {\it are} the legal entries for the 
{\:c GENERALIZATIONS}
 slot of
{\:c PRIMES, }
according to the distributed definition of 
{\:c GENERALIZATIONS} as {\:c GENL}$↑*$.

Notationally there is no distinction between slots which are ``primitive"
(values actually stored as attributes on a property list) and slots which
are ``virtual" (values must be computed using the slot's definition).
A heuristic might refer to the Generalizations of Primes without knowing,
or caring, whether that initiated a single access or a dizzy chase.
Thus we are decoupling, disentangling knowledge (the rules) from the
specific implementation of its representation (the choice of which slots
are primitive and which are virtual.) 
This is required because knowledge remains invariant under changes in
the environment which effect the worth of various representation schemes.
Michie recognized this long ago with his memo functions.

To define a new kind of slot, now, Eurisko merely specifies one of the
then-known
slot-combiners  and  a list of the old 
pre-existing slots from which it is built.
Thus we might define a new slot, by creating a new concept (calling it,
say, 
``{\:c DG}"), filling its
Slot-combiner slot with the entry ``Difference", filling its 
``Built-from" slot with the arguments ``Generalizations Genl."  This would
be a new kind of slot, one which returned all generalizations of a concept
except its immediate generalizations; the call 
{\:c (GET PRIMES DG)}
 would return
{\:c (PRIMES OBJECTS ANYTHING).   }

With no extension at all, Eurisko was then able to define new
kinds of slot-combiners. For instance, it proposed one which took
two old slotnames as arguments, f and g, and defined a new slot which was
f$↑*\circ\,$g$\,\circ\,$f$↑*$. This could be extremely useful (e.g., in database
searches: see Fiksel and Bower [1976]).  In particular the crucial
slot ``Examples" is defined as Spec$↑*\circ\,$Immed-Exs$\,\circ\,$Spec$↑*$.
{\:c PLUS} (in the sense of regular expressions, not arithmetic) is defined by
Eurisko as the difference between f$↑*$ and f.  Genl$↑+$ is found to
be more worthwhile than Genl$↑*$, and {\:c PLUS} itself is ultimately favored
over {\:c STAR.}

	\SSEC{CACHING to reclaim lost efficiency}

{\bf Summary:\  \sl 
``Caching'' the results of computations can dramatically improve the
performance of many programs.  Reasoning can be brought to bear to decide
whether to cache, if so what to remember, and (later) whether or not to ignore 
the cached value and recompute it.  Caching reclaims the efficiency that could
otherwise be sacrificed by the highly indirect representation-interpreting
scheme described in the previous section.
}


\yskip

The reader may object that Eurisko's scheme for indirectly interpreting the
definition of each slot is a horribly inefficient way to operate, since
the slots' definitions change so rarely. 
It seems absurd to squander cpu time recomputing {\:c (GET PRIMES
GENERALIZATIONS)} each time.  After at most one or two repetitions,
we would want our program to have ``learned'' an efficient way to get an
answer.

Indeed, a general tool for
cognitive economy
 --- software caching --- 
can be exploited to reclaim most of this efficiency.
By a  ``general" tool, we mean one which is applicable in almost all
environments, not merely those being focused upon in this paper (fluid ones.)

Immediately upon computing (GET c f), Eurisko store the computed value {\it v}
in the f slot of concept c ({\it a la} memo functions.)
Thus, the next time (GET c f) is called, it will
find {\it v} and return with it immediately.  After
(GET PRIMES GENERALIZATIONS) was called, the list (PRIMES NUMBERS OBJECTS
ANYTHING) was stored on the GENERALIZATIONS slot of PRIMES.  Recall that 
Eurisko had to recursively call (GET GENERALIZATIONS DEFN), so the
$\lambda$-expression {\it that} call returned would be stored on the
DEFN slot of the concept called GENERALIZATIONS.  When we later call
(GET DUCK GENERALIZATIONS), that call will run much faster, since the
definition of the Generalizations slot has already been computed and
stored away in the ``proper place.''
The definitions of
slots are very slowly --- if ever --- changing, hence the recomputation of
Defn of Generalizations is quite a rare event.  Caching that value must be
cost-effective in the long run.

In general, we see that caching a value for slot F of concept C is
most applicable when the value can be expected to vary quite infrequently.
In Eurisko, this gives us the flexibility to redefine a slot's definition
if we wish, but (since this change of representation
will be rare) the program will run just about as
efficiently as if that capability
were absent.  This is analogous to compiling: so long as the definition of
a function doesn't change too often, it's undisputedly worthwhile to compile
it.   The caching of 
{\:c DEFN}
 and
{\:c  GENERALIZATION}
 slots is not in any way special;
the value of any virtual slot can be cached.


We saw earlier that notationally 
there was no need
to distinguish an access of a primitively-stored slot from an access of a
virtual, computed slot.  E.g., a heuristic could refer to ``Generalizations
of Primes'' without knowing or caring whether that initiated a single access
or a long rippling search.
Now we see that once the value is computed and
cached away, there may be no telling it from a primitive one.
Thus, with but a small one-time cost, our program runs as quickly as if
all slots were primitive.  The inefficiency introduced by the
interpretive slot-combiner scheme has been eliminated.

The values that Eurisko caches away may become stale, incorrect after a
a while.  When doing a GET, therefore, when a cached value is encountered,
Eurisko must decide whether to accept it,
or else to ignore it, recompute it, and store the new value there.
One possible answer to this ``updating problem'' is the following
conservative one: whenever a value for a slot of a concept changes, discard any
cached values that might {\it possibly} have depended on it.
Arbitrary amounts of reasoning may be brought to bear to decide which
values needn't be discarded to maintain consistency of the knowledge base,
but of course if too mch time is spent in this pursuit the efficiency
advantages of caching disappear.  Eurisko carries on AM's tradition of
living with contradictions, with a plausible but not ``correct'' knowledge
base.  Namely, it has some heuristics (see Fig. 7)
for deciding whether to ignore or
accept any cache it encounters during a GET operation.

We added
some extra arguments to 
{\:c GET,}
 parameters which describe a
cost/benefit curve:
for each amount of resources expended and each
degree of precision of the result, this curve specifies precisely how
acceptable that resource consumption / accuracy of
solution pair is.   One extreme of this is to provide
an ironclad limit on resources
and say ``Do the best you can
within these time/space/... limits."  Another extreme
(most common in present-day programs) is to specify
an ironclad goal criterion (``Find an answer which is at
least {\sl this} good, no matter how long it takes to get.")
We are calling attention to the space in between
the two extremes.

To bring us back from the lofty heights of generality, let's see in more
detail how we got Eurisko to do this. 
First, we linearized this space:  we picked a
few significant parameters of it, and defined a description to be merely
a list of values for these parameters.
When a call on 
{\:c GET}
 was executed, and a cached value was encountered, a
formula relating these extra arguments to 
{\:c GET}
 would then determine whether
to accept that cache, or to ignore it and recompute the value.
Eurisko's parameters (extra arguments to 
{\:c GET}) are:
cpu time to expend, space to expend, whether the user can be asked about
this, how fresh the cache must be, minimum amount of resources which must have
been expended at the time the cache was written.

So
{\:c  (GET PRIMES GENERALIZATIONS 200 40 NIL 3 0)}
 would allow any cached
value to be accepted if it appeared that recomputing would take more than
200 milliseconds, or would use up more than 40 list cells, or if the value
had been put there less than three Cycles ago.\foo{In Eurisko, a ``Cycle'' is the
time it takes to work on the top-rated task on the top-rated agenda.}
Otherwise, the cache would be ignored, a newer value would be computed, and
it would be stored away.  With it would also be recorded the following information:
(i) the fact that it was
a cached value, not a primitive one, (ii) how long it took to compute,
(iii) how many list cells it used up in computing this value, (iv) the current
Cycle (number of tasks worked on so far). The above call on 
{\:c GET}
 might result
in the following value being stored on the 
{\:c GENERALIZATIONS}
 slot of 
{\:c PRIMES:}

{\:c (*cache* \  (PRIMES NUMBERS OBJECTS ANYTHING)  54  6  9).}


	      \SSSEC{Storing and Updating Cached Values}

The caching process involves storage and updating. For both of
these aspects, we can discuss details of when, why, how, and what.
The decisions that arise are made with the guidance of heuristic rules,
many of which are illustrated below in
Figs. 6 and 7.
We have omitted many of the
very general ``common-sense" heuristics, and those which deal with details
of Lisp programming. We also have specified the rules in English, rather than
in Lisp; we have freely used expressions like ``recently", although in any
encoding that would have to be made much more precise.

Finally, note that these heuristics are not {\it always} relevant; they are
applicable for many AI programs, running on 
uniprocessing
PDP-10-sized computers, running
Interlisp, with a human user watching and interacting.
There would be other rules for other machine architectures and languages.
In other words, one could say that we have only partially specified the
IF-part (left hand sides) of the following heuristic rules. An alternative
would be to build up an entire knowledge base of heuristics just to determine
the applicability, the domains of relevance, 
of the following (as a function of machine and language.)


\vfill\eject   % Because it takes 2 pages

.

\vfill

\vskip 5xgpin

\ctrline{\bf[FIGURE 6: PRINCIPLES FOR STORING CACHES]}

\yskip

\eject

.

\vfill

\vskip 5xgpin

\ctrline{\bf[FIGURE 6 (continued): PRINCIPLES FOR STORING CACHES]}

\yskip

\eject

.

\vfill

\vskip 5xgpin

\ctrline{\bf[FIGURE 7: PRINCIPLES FOR UPDATING CACHES]}

\yskip

\eject  % Just takes 1 page

	      \SSSEC{The Spectrum of Data Reductions}


Caching, as we have described it, is merely the lowest-level of a tier of
data reduction processes, techniques for compiling hindsight into usable,
{\it more efficient}, more procedural forms.

We often refer differently to ``caching''
depending upon what it is that's being retained:
open-ended, inductive searches can be condensed in hindsight (i.e. cached)
into heuristics, deductive searches can be cached into much less branchy
algorithms,
subroutines can be cached into tables of frequently called arguments and
resultant values, and variable quantities have their value cached simply by
the process of binding.
To see this, consider the progression of ever more sophisticated tasks
which programs perform [see Fig. 8]: accessing a datum, calculating a
value from a fast algorithm, deducing a result by searching for a solution
or proof in a well-defined space, 
inducing a result by a very open-ended search process.
Often there is the opportunity to take experiences at one of these levels of
sophistication and abstract them into an entity which is one level lower,
yet which appears to contain almost the same power. 

\vskip 2.7xgpin

\ctrline{\bf[FIGURE 8: Progression of caching]}

\yskip

Consider first the way in which we reduce induction. After
much experience with inducing, we produce a {\it heuristic rule} which
enables the same inferencing to be done in a much more controlled space,
in a much more deductive way.  Heuristics reduce discovery tasks to mere
(!) symbolic manipulation within a well-defined system (as in AM [Lenat 1976]).

Deduction is reduced similarly. By many painful deductions, we gain know\-ledge
of the space we are searching, e.g. by deriving many theorems about it.
Those theorems can then be used to vastly simplify our search. Ultimately,
the process becomes efficient calculation. A short, optimal algorithm may
be found, e.g., which replaces a search for a solution (this has recently
occurred with the ``{\sl n queens}'' chess problem.)

Now we see that our caching process is the next step in this progression.
It reduces a calculation (e.g., to traverse a particular access path to
gather all Ancestors of a node) by a lookup, by a single access of a datum
in memory.

All the data reduction processes in the progression are environment-independent
techniques for increasing cognitive economy.  Often, an apparent loss due
to a specific expressive feature can be rectified by applying some of
these kinds of methods.  In our case, we opted for interpretive defining
of slots, but regained efficiency by caching those slot definitions.

%also variable binding fits in?
%ACCESS==> CALCULATE ==> DEDUCE ==> INDUCE BY OPEN=ENDED SEARCH
%
%   \       /      \       /  \      /
%
%     cache          thm, alg   heur rule
%
%[[note: saving multiple
%instantiations of the same rule at different levels of abstraction is
%NOT worth mentioning, I think, since it is a STATIC (eg planning) tactic;
%I may be wrong, and perhaps we should at least mention this v. briefly anyway]]
%
%[[Should we metnion explcitly the loss that may occur if the task involves
%a lot of reasoning one's
%way through delicate inference chains efficiently; or: a lot of
%synthetic reasoning or rule interaction?]]
%

      \SSEC{Contrasts with Psychological Ideas of Economy}

    When semantic networks first appeared in cognitive psychology, they
led to the idea that function should follow form.  In particular,
since taxonomic knowledge structures were hierarchical, inference
processes would presumably follow the same inter-category network paths
each time the corresponding relation needed testing.  It was for this
reason that Collins & Quillian [1969][1972] conjectured
that the time required to verify semantic relations would correlate with
distance in a corresponding ``economical" semantic network.  Thus, they
showed that people ordinarily verified ``a canary is a bird" faster than
they could verify either of the two more remote relationships,
``a canary is an animal" or ``a canary has wings."

    Subsequent research however showed that the needs of
particular retrieval experiences,
not {\sl a priori} categorizations, determined which inference paths humans would
follow and the associated response times.
A simple counterexample to the presumed hierarchical
retrieval schemes was found by Rips, Shoben and Smith [1973].  They showed
that people access a familiar  but so-called ``indirect"
relation such as ``a dog is an animal"
much faster than the supposedly immediate but less frequent
relation ``a dog is a mammal."
Using experimental materials and methods, Hayes-Roth & Hayes-Roth [1975]
found that human memory seemed plastic and adaptive in many of the same ways
we have proposed for intelligent machine programs.  Their results led them
to ``an adaptive model of memory, in which all learned relations are
represented directly, with strength proportional to experience.  There is
also good evidence for redundancy in the network, with multiple routes
connecting nodes representing particular pairs of concepts" [1975, p. 519].

    In another study, Hayes-Roth and Hayes-Roth (1977) found some evidence
that people understand and remember English texts directly in terms
of high-level lexical concepts, rather than 
exclusively as low-level or primitive
concepts.  They argued that cognitive processes would presumably
benefit if they could build directly upon the words or other meaningful
units of familiar language.  Any system that interpreted and
stored data only in terms of primitive units, as is often assumed in
language understanding theories, would encounter many slower and costlier
searches.  Both the empirical evidence and theoretical principles support
the idea that human language understanding exploits many kinds of caching.

    In short, we have chosen the term ``caching" to refer to these types of
redundant storage.  Caching, to capture and exploit repetition and
regularity, will benefit both humans and machines of limited processing
capabilities.


\NSECP{When to Define a New Slot}

We have discussed
how a new slot {\it can} be defined; consider now how
Eurisko decides when and how   to define a new one.
Our basic reply to {\it When?}
is that a slot is defined only when a heuristic rule
explicitly suggest it as being useful; that is, heuristics are used as
plausible move generators (as opposed to their typical use [Nilsson 1972]
as implausible move pruners).  Our basic reply to {\it How?} is that the
heuristic which suggests a new slot must provide (constraints for) its definition.

This merely pushes the problem back one layer, namely to the way in which the
heuristics know when and how to define new slots.  But now we are talking the
language of AM and Eurisko, and we can provide examples and general characterizations
of the slot-defining heuristics used in Eurisko.  Since each type of slot is
represented internally as a full-fledged (schematized) concept,
the new slots defined can eventually be evaluated (and changed or
discarded if they are not utile).  Each heuristic is also represented as a full-fledged concept,
and {\it its} worth can be determined 
based on the worths of the slots it suggests; thus each slot-suggesting heuristic
is occasionally modified (or even discarded).  Let's look at some cases:

Sometimes the
new type of slot is first proposed purely for aesthetic, analogy-completing, or
exploratory reasons. One such heuristic is:

\noindent ``If R and S are partial inverses of each other, then it's plausible
to define and investigate the following: 
R$\circ$S, S$\circ$R.''
% R$\circ$S -- $i$, S$\circ$R -- $i$  (where $i$ is the identity mapping,) 

There are several noneffective slots provided for the above heuristic in
Eurisko, such as its reason (``aesthetic''), its average running time,
which other rule(s) created {\it it} originally, instances of its use, etc.

Note that the heuristic
applies when R and S are mathematical functions, heuristics, or
slot definitions.  In the latter case, which is of concern to us, when
R is the slot ``Generalizations'' and S is the slot ``Specializations,''
this rule concludes that
it's aesthetic to define ``siblings'' (the
specializations of the generalizations of a concept) and
``inlaws'' (the generalizations of the specializations of a concept.)
Eventually, the former slot is seen to be much more useful than the latter,
which is discarded.


The new kind of slot-combiner
defined in the previous section
($\lambda\ (f,g)\ f↑*\circ\,g\,\circ\,f↑*$), 
was derived purely from symmetry (using a rule similar to this one),
and then it was noticed that some of the
slots which are most useful in the system (e.g., Isas, Examples) share that common
form. 


The definition of a new slot is often based
soundly upon need --- or the absence of need.  For example,

\noindent ``If, by monitoring usage, you notice
notice that many concepts have a large number of entries for their {\:c F} slot,
Then consider creating some new specializations of
{\:c F}.''

When applied, this leads Eurisko to create
several new slots, each having
fewer entries on the average than {\:c F} had, to cover the original {\:c F} slot.
E.g., after noting that the Examples slot was heavily used,
it would be plausible to consider creating new slots like Extreme-examples
and 
Typical-examples.  

A slightly more specialized heuristic says:

\noindent ``If you frequently perform `Remove x from f(x)', Then
it's plausible to define g as f -- $i$"  

Here, {\it i} is the
identity, so g(x) is simply f(x) with x removed.
This leads to the definition of
the proper ancestor slot (Genl$↑*$(c) -- c) from the simplerGenl slot,
to the definition
of the slot-combiner PLUS from STAR, and 
of many common, useful
mathematical functions, including
(although Eurisko doesn't actually
do this)
operations on matrices with main diagonals removed.

The above examples should adequately illustrate the manner in which
heuristic rules can generate timely new kinds of slots. A very important
point is that the rules are not specific to defining slots; they apply
equally well to defining new heuristics, new mathematical functions,
new lab procedures, and so on.
One of the bedrock philosophies of the Eurisko effort is that a single
large core of commonsense knowledge can  adequately guide discovery
processes operating on all these levels.

\NSECP{Conclusions}


If forced to survive in a changing world,
most inferential systems could benefit
from
{\it learning}
about their task environment and their own behavior.  For example,
they can exploit new schemata or different slot-names to simplify and
restructure their knowledge.  Self-modification would be cognitively
economical.

If forced to explore large
search spaces with some repetitive regularity, a
cognitive system could benefit by employing
{\it caching}
to save partial results.  We described a variety of techniques to
implement caching, and explained how caching specific results is
one of a spectrum of methods that can make trade-offs among precision,
speed, certainty, and generality.  

Since most environments contain much that is extraneous to the direct
solution of a task, a problem solver in such worlds can gain cognitive
economy by
{\it expectation-filtering} (see Appendix 5.1.)
In general, intelligent systems need to exploit their knowledge about
typicality to reduce their cognitive load and increase their attention
to important data.  In many situations, we believe that expectations
can both reduce processing requirements for handling ordinary events
as well as simplify the identification of surprising events.  

If the tasks are complex, and the resources alloted vary dramatically in magniude,
then
{\it multiple levels of abstraction} (MLA)
becomes  an {\it economical} representation (see Appendix 5.2.)  In many simple
environments, the advantages of MLA are minimal
and may not even justify their costs.  Thus, routine tasks may
warrant the kind of knowledge compilation that would convert an initial,
expressive MLA knowledge-base into a fast, integrated, and largely
uninterpretible code.  Conversely, as task complexity and variability
increase, MLA increasingly provides a basis for intelligent and rapid
restructuring.

	\SSEC{The Need for Further Research}

    In the years to come, AI programs will employ greatly expanded
knowledge bases and, as a consequence, they will explore increasingly
open-ended problem spaces.  Already, a few existing systems show signs
of having more potentially interesting things to do than they have
resources to pursue (e.g., AM, Eurisko).  In the past decades of
intelligent systems R&D, several design concepts have emerged in
response to contemporary needs for creating ever larger knowledge
bases.  For example, many researchers proposed multiple levels of
abstraction and automatic property inheritance as keystones of
efficiency or ``cognitive economy."  We believe that the value of such
mechanisms derives largely from their usefulness in describing initial
knowledge bases.  Once an intelligent system begins to explore the
consequences of its knowledge and to solve novel problems in a
dynamic environment, it needs to adapt its knowledge to achieve
faster and more profitable retrievals.

We have tried to show what cognitive economy
{\it is}
and
{\it is not.}
It does
{\it not}
consist of a set of static knowledge-base design principles, such
as those proposing taxonomic concept structures with automatic
property inheritance.  Rather, cognitive economy is a feature of
those intelligent systems that learn to solve problems efficiently
and consequently realize more of their lifetime potential.  
As knowledge
bases expand and basic software obstacles are overcome, AI systems
will increasingly address the same question facing intelligent
humans:  ``What would I most like to accomplish next, and how can I do that
economically?"

     A theory of cognitive economy
should explain 
under what conditions (and why)
knowledge needs to be adapted, and should prescribe systematically
how to do it.  In this paper, we have tried to
motivate and lay the groundwork for such a
theory.  
We presented Eurisko's automatic defining of plausible, useful new
slot types.
Many of the design heuristics we mentioned embody some gross features of
an eventual
theory and suggest numerous paths for future research.


\vskip 1xgpin 	% acknowledgements

{\bf Acknowledgements}

\vskip .6xgpin

\ninepoint

\parindent 19pt

We wish to thank Dave Barstow, John Seely Brown, Bruce Buchanan, Ed Feigenbaum, 
Cordell Green, Greg Harris, Barbara
Hayes-Roth, Allen Newell, Herbert Simon, 
and Don Waterman for several discussions which have left their
mark in this paper.

\setcount4 0	%  Reset for start of Appendices